/**
 * @author : HESS MArjorie, THUILLIER Jules, G4 - CIP2
 */
package ArbreBinaire;

/*
 * Classe d’implémentation d’ArbreBinaireOrdonné à l’aide d’une structure chaîné
 *
 */

public class ArbreBinaireOrdonneChaine<T> implements ArbreBinaireOrdonne<T> {
	public ArbreBinaire<T> a = ArbreBinaireChaine.arbreVide;
	/**
     * Rôle : construit une table vide d’<code>Élément<V,C></code>
     */
	public ArbreBinaireOrdonneChaine() {
	        this.a = ArbreBinaireChaine.arbreVide;
	}
   /**
     * Rôle : Ajouter en feuille dans l’arbre ordonné courant
     *        l’élément e, si celui si n’est pas déjà présent.
     *        La méthode retourne une référence sur le noeud de l’élément e.
     */
	
	public ArbreBinaire<T> ajouter(T e) {
		try {
			ArbreBinaire<T> p = null, q = a;
			while (!q.estVide()) { 
				p=q;
				if (((Comparable) e).compareTo(q.valeur())==0) 
					// l’élément e est déjà présent
					return q;
				else
					if (((Comparable) e).compareTo(q.valeur())<0)
						q=q.sag();
					else
						q=q.sad();
			}
			// q=ArbreBinaireChaîné.arbreVide et p désigne 
			// le noeud auquel il faut attacher e
			q = new ArbreBinaireChaine<T>(e);
			if (p==null) // l’arbre est vide
				a=q;
			else
				if (((Comparable) e).compareTo(p.valeur())<0) // on le met à gauche
					p.changerSag(q);
				else // on le met à droite 
					p.changerSad(q);
			return q; 
		}
		catch (ArbreVideException ex) {System.err.println(ex); } 
		// pour faire plaisir au compilateur
		return null;
	}
	
	
	
	/**
	 * Rôle : Ajouter en feuille dans l’arbre ordonné courant l’élément e
	 *        méthode, version itérative
	 *
	 */
	public void ajouterEnFeuilleI(T e){
		ArbreBinaire<T> p,q;
		try {
			q=a; p=null;
			while (!q.estVide()) {
				p=q;
				if (((Comparable) e).compareTo(q.valeur())<=0)
					q=q.sag();
				else
					q=q.sad();
			}
			// q=ArbreBinaireChaîné.arbreVid et p désigne 
			// le noeud auquel il faut attacher e
			q = new ArbreBinaireChaine<T>(e);
			if (a.estVide()) // l’arbre est vide
				a=q;
			else
				if (((Comparable) e).compareTo(q.valeur())<=0) // on le met à gauche
					p.changerSag(q);
				else // on le met à droite 
					p.changerSad(q);
		}
		catch (ArbreVideException ex) {System.err.println(ex); } 
	}
	
	
	/**
	 * Rôle : Ajouter en feuille dans l’arbre ordonné courant l’élément e * méthode, version récursive
	 *
	 */
	
	
	public void ajouterEnFeuilleR(T e) {
		try {
			a = ajouterEnFeuilleR(a, e);
		}
		catch (ArbreVideException ex) { }
	}
	
	protected ArbreBinaire<T> ajouterEnFeuilleR(ArbreBinaire<T> a, T e) throws ArbreVideException{
		if (a.estVide())
			return new ArbreBinaireChaine<T>(e);
		// a n’est pas vide
		if (((Comparable) a.valeur()).compareTo(e)<0){
		    // clé du noeud courant  >= e.clé
			// ajouter dans le sous−arbre gauche
			a.changerSag(ajouterEnFeuilleR(a.sag(), e));
		}
		else if(( (Comparable) a.valeur()).compareTo(e)>0){
			// clé du noeud courant  < e.clé
			// ajouter dans le sous−arbre droit
			a.changerSad(ajouterEnFeuilleR(a.sad(), e));
		}
	return a;
	}
	
	
	public String toString() {
		return this.a.toString();
	}
}
